A problem faced by many travelers in the physical world relates to choosing a route between a source location and destination location. Several computer-implemented applications have been developed to assist travelers in making such choice. For example, computer-executable applications have been developed to identify a travel route between specified source and destination locations. These computer-executable applications utilize a graph to represent a road network, where road segments are represented by respective weighted edges. A weight assigned to an edge can be indicative of, for example, the expected amount of time it will take to travel over a road segment represented by the edge (e.g., which may be a function of a speed limit assigned to the road segment, expected traffic over the road segment, or a observed traffic over the road segment). The computer-executable application searches the graph for the route between the source location and the destination location that has the lowest aggregate cost from amongst all possible routes. The computer-executable application then outputs the identified route to a user.
There are many analogous applications, however, where it is difficult to ascertain weights to assign to edges in the graph prior to acquiring observations for these edges. As one of many examples, a robot may attempt to travel from a source location to a destination location over unexplored terrain in a region. For instance, the robot may have rough information about treacherous regions of the terrain that would risk slowing the robot, but may not have granular information about the entirety of the terrain. The robot, accordingly, must attempt to identify an optimal route to reach the destination location by using sparse data and observations captured by the robot as it travels. In another example, efficiency of air transport is sensitive to winds encountered over the course of a flight. Airplane pilots typically travel at a constant, recommended airspeed for their aircraft based upon engine, altitude, and weight. Given a fixed airspeed, tailwinds and headwinds increase and decrease, respectively the ground speed of aircraft. Pilots, in collaboration with air traffic control and in accordance with airline policies, establish and modify flight plans to avoid turbulence and to seek favorable winds.
Wind forecasts available for flight planning have conventionally been limited to the use of relatively coarse information, where wind speed and direction are detected by sparsely situated weather balloons. Linear interpolation has been employed to estimate wind directions and velocities in segments over which airplanes may travel. Thus, a region through which an airplane is capable of travelling can be modeled as a computer-implemented graph, wherein the graph has edges representative of travel segments, and the edges have weights that are respectively based upon estimated wind speeds and directions. Due to sparseness of sensors in the region, however, exact wind information is unavailable for many of the travel segments—thus, wind information for a travel segment may be unknown prior to an airplane traversing the segment.
Conventionally, the above-described graphs that represent real world travel routes have been assigned weights that are discrete and independent of one another. While this conventional approach is well-suited for applications where a large amount of sensor data has been collected and weights of edges are generally known, this approach is not particularly well-suited for identifying optimal routes in a region where collected data is somewhat sparse (and possibly subject to rapid change, such as wind speed and direction, water current speed and direction, etc.).